package leetcode.editor.cn.q1_300.q;

import java.util.ArrayList;
import java.util.List;

/**
 * @author qidi
 * @date 2021-11-03 14:09:30
 */
class Q0029_DivideTwoIntegers {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int divide(int dividend, int divisor) {
            if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

            if (dividend == divisor) return 1;

            if (divisor == Integer.MIN_VALUE) return 0;

            // 全部转变负数
            int a = dividend;
            int b = divisor;
            if (dividend > 0) a = -dividend;
            if (divisor > 0) b = -divisor;

            // 每次减法的结果
            int diff = a;
            // 统计的结果
            int res = 0;
            // 当前除数最大的倍数
            int tmp = 1;
            // 当前的除数
            int div = b;

            List<Integer> tmps = new ArrayList<>();
            List<Integer> divs = new ArrayList<>();

            divs.add(div);
            tmps.add(tmp);

            while (diff <= b) {
                div += div;
                tmp += tmp;

                divs.add(div);
                tmps.add(tmp);

//                if (div == 0)
                diff -= div;
            }

            for (int i = divs.size() - 2; i >= 0; ) {
                if (a <= divs.get(i)) {
                    res += tmps.get(i);
                    a -= divs.get(i);
                } else {
                    i--;
                }
            }

            if (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0) res = -res;
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0029_DivideTwoIntegers().new Solution();
//        System.out.println(solution.divide(10, 3));
//        System.out.println(solution.divide(10, -3));
//        System.out.println(solution.divide(-10, 3));
//        System.out.println(solution.divide(-10, -3));
//        System.out.println(solution.divide(1, 1));
        System.out.println(Integer.MIN_VALUE - Integer.MIN_VALUE);
        System.out.println(solution.divide(Integer.MIN_VALUE, Integer.MIN_VALUE));
    }
}